﻿/************************************************************************

   Extended Silverlight Toolkit

   Copyright (C) 2010-2012 Xceed Software Inc.

   This program is provided to you under the terms of the Microsoft Public
   License (Ms-PL) as published at http://extendedsilverlight.codeplex.com/license

   Please purchase a commercial version of this toolkit if you are using
   it in a commercial product. The commercial versions support the project,
   and also include more features for each control, priority support,
   source code, updates, removed watermark, and a proprietary license.

   Visit http://xceed.com and follow @datagrid on Twitter.

  **********************************************************************/

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.Linq;

namespace Xceed.Silverlight.Data
{
  internal class SortPositionFinderEnumerator<T> : AsyncParentEnumerator<T> where T : RawDataItem
  {
    #region Static Fields

    private const long UnknownSize = 1000;

    private static readonly Guid JumpMoveAndFetchCallId = DataUtils.CreateCallId();
    private static readonly Guid GetDataSourceSizeCallId = DataUtils.CreateCallId();
    private static readonly Guid EstimateDataSourceSizeCallId = DataUtils.CreateCallId();
    private static readonly Guid FindPositionCallId = DataUtils.CreateCallId();
    private static readonly Guid BinarySearchCallId = DataUtils.CreateCallId();

    #endregion Static Fields

    #region Constructor

    internal SortPositionFinderEnumerator(
      IAsyncEnumerator childEnumerator,
      DataSourceProvider dataSourceProvider,
      IContextualCompareHelper<T> compareHelper )
      : base( childEnumerator )
    {
      if( dataSourceProvider == null )
        throw new ArgumentNullException( "dataSourceProvider" );

      if( compareHelper == null )
        throw new ArgumentNullException( "compareHelper" );

      m_dataSourceProvider = dataSourceProvider;
      m_compareHelper = compareHelper;
    }

    #endregion

    public override JumpMoveAndFetchAsyncResult BeginJumpMoveAndFetch(
      JumpMoveAndFetchParameters parameters,
      AsyncCallback callback,
      object state )
    {
      this.CheckMoveAndFetchParameters( parameters.ExpectedMoveCount, parameters.ExpectedFetchCount );

      JumpMoveAndFetchAsyncResult asyncResult = new JumpMoveAndFetchAsyncResult(
                                                  SortPositionFinderEnumerator<T>.JumpMoveAndFetchCallId,
                                                  callback,
                                                  state,
                                                  parameters );

      if( !this.HandleSortPosition( asyncResult, parameters ) )
      {
        // This anonymous method calls the underlying enumerator.
        Func<AsyncCallback, object, IAsyncResult> beginJumpMoveAndFetch =
          ( cb, st ) => base.BeginJumpMoveAndFetch( parameters, cb, st );

        // This anonymous method gets the result from the underlying enumerator.
        Func<AsyncResult, IAsyncResult, DependentCallResult> endJumpMoveAndFetch =
          ( par, iar ) => new DependentCallResult( base.EndJumpMoveAndFetch( ( JumpMoveAndFetchAsyncResult )iar ) );

        asyncResult.Start( beginJumpMoveAndFetch, endJumpMoveAndFetch );
      }

      return asyncResult;
    }

    public override JumpMoveAndFetchResult<T> EndJumpMoveAndFetch(
      JumpMoveAndFetchAsyncResult asyncResult )
    {
      asyncResult.ValidateCallEnd( SortPositionFinderEnumerator<T>.JumpMoveAndFetchCallId );

      return asyncResult.GetCallResult<JumpMoveAndFetchResult<T>>();
    }

    protected override void Dispose( bool disposing )
    {
      m_disposed = true;

      base.Dispose( disposing );
    }

    private bool HandleSortPosition(
      JumpMoveAndFetchAsyncResult asyncResult,
      JumpMoveAndFetchParameters parameters )
    {
      // There is nothing to handle here if the position isn't a SortPosition.
      SortPosition sortPosition = parameters.SourcePosition as SortPosition;
      if( sortPosition == null )
        return false;

      // There is nothing to handle here if the DataSourceProvider is already able
      // to do the job itself.
      IEnumerable<SortDescription> sortedProperties = sortPosition.SortingReference.Take( sortPosition.SortValues.Count );
      if( m_dataSourceProvider.CanJumpTo( sortedProperties ) )
        return false;

      bool isNavigationFilterSupported = NavigationFilterUtils.IsSupported( m_dataSourceProvider, sortPosition.SortingReference );

      // There is nothing to handle here if the SortPosition may be replaced by a 
      // FilterExpression that will produce the same result without any impact 
      // on the primary key value of the items.
      if( ( isNavigationFilterSupported ) && ( !m_dataSourceProvider.IsPrimaryKeyVolatile ) )
        return false;

      // The DataSourceProvider must support skipping if we want our search algorithm
      // to be efficient.
      if( !m_dataSourceProvider.CanSkip )
        throw new InvalidOperationException( "An attempt was made to use a DataSourceProvider that does not support skipping." );

      List<string> sortedPropertyNames = sortedProperties.Select( ( item ) => item.PropertyName ).Distinct().ToList();
      bool isTargetingAnItem = ( from pk in m_dataSourceProvider.PrimaryKeyInfo
                                 select sortedPropertyNames.Contains( pk.PropertyName ) ).All( ( result ) => result );
      bool isQueryingForward = DataUtils.IsQueryingForward( parameters.ExpectedMoveCount, parameters.ExpectedFetchCount );
      DataSourceContext context = parameters.Context;

      // Before looking for the position, evaluate the data source size
      // to bound the search.
      asyncResult.AddDependentCall(
        ( cb, st ) => this.BeginGetDataSourceSize( context, cb, st ),
        ( par, iar ) => new DependentCallResult( this.EndGetDataSourceSize( iar ) ) );

      // Search for the index of the target position in the data source.
      asyncResult.AddDependentCall(
        ( cb, st ) => this.BeginFindPosition( context, sortPosition, isTargetingAnItem, isQueryingForward, ( long )st, cb, st ),
        ( par, iar ) =>
        {
          long position = this.EndFindPosition( iar );

          if( m_disposed )
            return new DependentCallResult( null );

          return this.HandleSortPositionResult( parameters, position );
        } );

      asyncResult.Start();

      return true;
    }

    private IAsyncResult BeginGetDataSourceSize( DataSourceContext context, AsyncCallback callback, object state )
    {
      AsyncResult asyncResult = new AsyncResult(
                                  SortPositionFinderEnumerator<T>.GetDataSourceSizeCallId,
                                  callback,
                                  state );

      // These anonymous methods try to get the data source size from a data query.
      Func<AsyncCallback, object, IAsyncResult> beginGetDataSourceSize =
        ( cb, st ) => this.BeginEstimateDataSourceSize( context, cb, st );
      Func<AsyncResult, IAsyncResult, DependentCallResult> endGetDataSourceSize =
        ( par, iar ) => new DependentCallResult( this.EndEstimateDataSourceSize( iar ) );

      if( m_dataSourceProvider.CanCount )
      {
        // These anonymous methods try to get the data source size from a count query.
        Func<AsyncCallback, object, IAsyncResult> beginGetDataSourceSizeFromCountQuery =
          ( cb, st ) => this.BeginCount( new CountParameters( context ), cb, st );
        Func<AsyncResult, IAsyncResult, DependentCallResult> endGetDataSourceSizeFromCountQuery =
          ( par, iar ) =>
          {
            CountResult countResult = this.EndCount( iar );

            if( ( countResult != null ) && ( countResult.Count != null ) )
              return new DependentCallResult( countResult.Count.Value );

            if( m_disposed )
              return new DependentCallResult( null );

            return new DependentCallResult(
                      null,
                      beginGetDataSourceSize,
                      endGetDataSourceSize );
          };

        asyncResult.Start(
          beginGetDataSourceSizeFromCountQuery,
          endGetDataSourceSizeFromCountQuery );
      }
      else
      {
        asyncResult.Start(
          beginGetDataSourceSize,
          endGetDataSourceSize );
      }

      return asyncResult;
    }

    private long EndGetDataSourceSize( IAsyncResult asyncResult )
    {
      asyncResult.ValidateCallEnd( SortPositionFinderEnumerator<T>.GetDataSourceSizeCallId );

      if( m_disposed )
        return 0;

      return asyncResult.GetCallResult<long>();
    }

    private IAsyncResult BeginEstimateDataSourceSize( DataSourceContext context, AsyncCallback callback, object state )
    {
      AsyncResult asyncResult = new AsyncResult(
                                  SortPositionFinderEnumerator<T>.EstimateDataSourceSizeCallId,
                                  callback,
                                  state );

      Debug.Assert( SortPositionFinderEnumerator<T>.UnknownSize > 0 );

      long position = SortPositionFinderEnumerator<T>.UnknownSize;

      Func<AsyncCallback, object, IAsyncResult> beginTestDataSourceSize = null;
      beginTestDataSourceSize =
        ( cb, st ) =>
        {
          JumpMoveAndFetchParameters parameters = new JumpMoveAndFetchParameters(
                                                    SourcePosition.BeforeFirst,
                                                    position,
                                                    0,
                                                    context );

          return base.BeginJumpMoveAndFetch( parameters, cb, st );
        };

      Func<AsyncResult, IAsyncResult, DependentCallResult> endTestDataSourceSize = null;
      endTestDataSourceSize =
        ( par, iar ) =>
        {
          JumpMoveAndFetchResult<T> result = base.EndJumpMoveAndFetch( ( JumpMoveAndFetchAsyncResult )iar );

          if( ( result != null ) && ( result.TotalCount != null ) )
            return new DependentCallResult( result.TotalCount.Value );

          if( ( m_disposed ) || ( result == null ) || ( !result.Result ) )
            return new DependentCallResult( position );

          try
          {
            checked
            {
              position *= 2;
            }
          }
          catch( OverflowException )
          {
            return new DependentCallResult( long.MaxValue );
          }

          return new DependentCallResult(
                   null,
                   beginTestDataSourceSize,
                   endTestDataSourceSize );
        };

      asyncResult.Start( beginTestDataSourceSize, endTestDataSourceSize );

      return asyncResult;
    }

    private long EndEstimateDataSourceSize( IAsyncResult asyncResult )
    {
      asyncResult.ValidateCallEnd( SortPositionFinderEnumerator<T>.EstimateDataSourceSizeCallId );

      return asyncResult.GetCallResult<long>();
    }

    private IAsyncResult BeginFindPosition(
      DataSourceContext context,
      SortPosition targetPosition,
      bool isTargetingAnItem,
      bool isQueryingForward,
      long dataSourceSize,
      AsyncCallback callback,
      object state )
    {
      AsyncResult asyncResult = new AsyncResult(
                                  SortPositionFinderEnumerator<T>.FindPositionCallId,
                                  callback,
                                  state );

      if( ( !m_disposed ) && ( dataSourceSize > 0 ) )
      {
        asyncResult.Start(
          ( cb, st ) => this.BeginBinarySearch( context, targetPosition, isTargetingAnItem, isQueryingForward, 1, dataSourceSize, cb, st ),
          ( par, iar ) => new DependentCallResult( this.EndBinarySearch( iar ) ) );
      }
      else
      {
        asyncResult.StartSync( 0L );
      }

      return asyncResult;
    }

    private long EndFindPosition( IAsyncResult asyncResult )
    {
      asyncResult.ValidateCallEnd( SortPositionFinderEnumerator<T>.FindPositionCallId );

      return asyncResult.GetCallResult<long>();
    }

    private IAsyncResult BeginBinarySearch(
      DataSourceContext context,
      SortPosition targetPosition,
      bool isTargetingAnItem,
      bool isQueryingForward,
      long lowerBound,
      long upperBound,
      AsyncCallback callback,
      object state )
    {
      Debug.Assert( lowerBound <= upperBound );

      AsyncResult asyncResult = new AsyncResult(
                                  SortPositionFinderEnumerator<T>.BinarySearchCallId,
                                  callback,
                                  state );
      long center = 0;

      // These anonymous methods do a binary search possibly asynchronously.
      // The algorithm may fail when the calls are asynchronous and the
      // data source changes while searching.
      Func<AsyncCallback, object, IAsyncResult> beginSearch = null;
      beginSearch =
        ( cb, st ) =>
        {
          center = lowerBound + ( upperBound - lowerBound ) / 2;

          JumpMoveAndFetchParameters parameters = new JumpMoveAndFetchParameters(
                                                    SourcePosition.BeforeFirst,
                                                    center,
                                                    0,
                                                    context );

          return base.BeginJumpMoveAndFetch( parameters, cb, st );
        };
      Func<AsyncResult, IAsyncResult, DependentCallResult> endSearch = null;
      endSearch =
        ( par, iar ) =>
        {
          JumpMoveAndFetchResult<T> result = base.EndJumpMoveAndFetch( ( JumpMoveAndFetchAsyncResult )iar );

          if( ( m_disposed ) || ( result == null ) )
            return new DependentCallResult( 0L );

          SourcePosition endPosition = result.EndPositionObject;
          int compare;

          if( endPosition is ItemPosition )
          {
            T item = ( ( ItemPosition )endPosition ).Item as T;
            compare = m_compareHelper.Compare( context, targetPosition, item );

            if( ( isTargetingAnItem ) && ( compare != 0 ) )
            {
              SortPosition itemBound = new SortPosition(
                                         targetPosition.SortingReference,
                                         targetPosition.SortValues,
                                         ( targetPosition.StartPosition == StartPosition.Before )
                                           ? StartPosition.After
                                           : StartPosition.Before );

              int compareItemBound = m_compareHelper.Compare( context, itemBound, item );

              // The item has been found.
              if( compareItemBound != compare )
              {
                compare = 0;
              }
            }

            // The targeted position has been found.
            if( compare == 0 )
            {
              long firstItemOffset = 0;

              // The current item is the one that comes prior to the first desired item.
              // Find out the offset to apply to get to the first item.
              if( ( targetPosition.StartPosition == StartPosition.Before ) != ( isQueryingForward ) )
              {
                firstItemOffset = ( isQueryingForward ) ? 1 : -1;
              }

              return new DependentCallResult( center + firstItemOffset );
            }
          }
          // The target position is before the first item of the data source.
          else if( endPosition.IsBeforeFirst )
          {
            return new DependentCallResult( 0L );
          }
          else if( endPosition.IsAfterLast )
          {
            // The target position is after the last item of the data source.
            if( lowerBound >= upperBound )
              return new DependentCallResult( center );

            compare = 1;
          }
          else
          {
            throw new DataInternalException();
          }

          Debug.Assert( compare != 0 );

          if( compare < 0 )
          {
            upperBound = center - 1;
          }
          else
          {
            lowerBound = center + 1;
          }

          // There is no more item to test.
          if( lowerBound > upperBound )
          {
            long targetBound = ( isQueryingForward )
                                 ? lowerBound
                                 : upperBound;

            return new DependentCallResult( targetBound );
          }
          else
          {
            return new DependentCallResult( null, beginSearch, endSearch );
          }
        };

      asyncResult.Start( beginSearch, endSearch );

      return asyncResult;
    }

    private long EndBinarySearch( IAsyncResult asyncResult )
    {
      asyncResult.ValidateCallEnd( SortPositionFinderEnumerator<T>.BinarySearchCallId );

      return asyncResult.GetCallResult<long>();
    }

    private DependentCallResult HandleSortPositionResult(
      JumpMoveAndFetchParameters parameters,
      long targetPosition )
    {
      int fetchCount = parameters.ExpectedFetchCount;
      long moveCount = targetPosition + parameters.ExpectedMoveCount;
      SortPosition targetSortPosition = parameters.SourcePosition as SortPosition;

      // Since a SortPosition swallow one move to get on the next item, we may need
      // to corrected the move counter.
      if( targetSortPosition != null )
      {
        moveCount -= Math.Sign( parameters.ExpectedMoveCount );
      }

      // We cannot start a query that doesn't move or fetch.  We'll have
      // to fetch at least one element.
      if( moveCount == 0 && fetchCount == 0 )
      {
        fetchCount = 1;
      }

      JumpMoveAndFetchParameters newParameters = new JumpMoveAndFetchParameters(
                                                   SourcePosition.BeforeFirst,
                                                   moveCount,
                                                   fetchCount,
                                                   parameters.ApproximateMove,
                                                   parameters.Context );

      // This anonymous method will start the query on the child enumerator.
      Func<AsyncCallback, object, IAsyncResult> beginQuery =
        ( cb, st ) => base.BeginJumpMoveAndFetch( newParameters, cb, st );

      // This anonymous method will convert the result of the query to the initial
      // requested query format.
      Func<AsyncResult, IAsyncResult, DependentCallResult> endQuery =
        ( par, iar ) =>
        {
          JumpMoveAndFetchAsyncResult asyncResult = ( JumpMoveAndFetchAsyncResult )iar;
          JumpMoveAndFetchAsyncResult parentAsyncResult = ( JumpMoveAndFetchAsyncResult )par;
          JumpMoveAndFetchResult<T> completeResult = base.EndJumpMoveAndFetch( asyncResult );

          if( completeResult == null )
            return new DependentCallResult( null );

          // The move failed.  We must find out the actual move count.
          Nullable<long> actualMoveCount;
          if( completeResult.FetchedItems == null )
          {
            if( completeResult.ActualMoveCount.HasValue )
            {
              long actualMoveOffset = targetPosition;

              // We must take into account the move that is swallowed by the SortPosition
              // for the actual move count calculation.
              if( targetSortPosition != null )
              {
                if( ( completeResult.ExpectedMoveCount != 0 )
                  && ( completeResult.ExpectedMoveCount != completeResult.ActualMoveCount ) )
                {
                  actualMoveOffset -= Math.Sign( completeResult.ExpectedMoveCount );
                }
                // We have to take into account the extra move that got us out of bound.
                else
                {
                  actualMoveOffset -= Math.Sign( parameters.ExpectedMoveCount );
                }
              }

              actualMoveCount = completeResult.ActualMoveCount.Value - actualMoveOffset;
            }
            else
            {
              actualMoveCount = null;
            }
          }
          // The move succeeded.
          else
          {
            actualMoveCount = parentAsyncResult.ExpectedMoveCount;
          }

          // Remove the item fecthed if we had to fake the fetch part.
          ICollection<T> fetchedItems = completeResult.FetchedItems;
          if( ( parentAsyncResult.ExpectedFetchCount != fetchCount )
            && ( fetchedItems != null )
            && ( fetchedItems.Count > 0 ) )
          {
            fetchedItems = new List<T>( 0 );
          }

          return new DependentCallResult(
                   new JumpMoveAndFetchResult<T>(
                     parentAsyncResult,
                     actualMoveCount,
                     fetchedItems,
                     completeResult.Result,
                     completeResult.EndPositionObject,
                     completeResult.EndPositionOffset,
                     completeResult.TotalCount ) );
        };

      return new DependentCallResult( null, beginQuery, endQuery );
    }

    #region Private Fields

    private readonly DataSourceProvider m_dataSourceProvider;
    private readonly IContextualCompareHelper<T> m_compareHelper;
    private bool m_disposed; //false

    #endregion
  }
}
